//
// Created by LiuYou on 2021/5/24.
//

#include <unordered_map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <climits>

static std::pair<std::string, int> findLowestCostNode(std::__umap_hashtable<std::string, int>& cost);

static void DijkstraAlgorithm(std::__umap_hashtable<std::string, std::__umap_hashtable<std::string, int>>& graph,
                              std::__umap_hashtable<std::string, int>& costs,
                              std::__umap_hashtable<std::string, std::string>& parent,
                              std::vector<std::pair<std::string, int>>& processed);

/**
 * @brief 这是一个失败的狄克斯特拉算法, 见2。
 * @return
 */
int main() {
    // 使用散列表存储邻居和前往邻居的开销
    std::__umap_hashtable<std::string, std::__umap_hashtable<std::string, int>> graph;
    graph["start"] = {};
    graph["start"]["a"] = 6;
    graph["start"]["b"] = 2;

    std::cout << graph["start"]["a"] << std::endl;
    std::cout << graph["start"]["b"] << std::endl;

    graph["a"] = {};
    graph["a"]["final"] = 1;
    graph["b"] = {};
    graph["b"]["a"] = 3;
    graph["b"]["final"] = 5;
    graph["final"] = {};

    // 使用散列表存储每个结点的开销
    std::__umap_hashtable<std::string, int> costs;
    costs["a"] = 6;
    costs["b"] = 2;
    // py中可以表示无穷大, 但是C++中设置一个标志数即可。这里我设置成了 -1 。
    // 不行, 这里不能设置为 -1 , 因为后续操作算法要对cost哈希表中的元素比较大小！！！！
    costs["final"] = INT_MAX;

    // 还需要一个散列表, 这个散列表存储父结点
    std::__umap_hashtable<std::string, std::string> parent;
    parent["a"] = "start";
    parent["b"] = "start";
    parent["final"] = "";

    // 还需要一个数组来记录处理过的结点。
    std::vector<std::pair<std::string, int >> processed;
    DijkstraAlgorithm(graph, costs, parent, processed);

    for (const auto& item : parent) {
        std::cout << item.second << std::endl;
    }


    std::exit(0);
}

static void
DijkstraAlgorithm(std::__umap_hashtable<std::string, std::__umap_hashtable<std::string, int>>& graph,
                  std::__umap_hashtable<std::string, int>& costs,
                  std::__umap_hashtable<std::string, std::string>& parent,
                  std::vector<std::pair<std::string, int>>& processed) {
//     下面实现狄克斯特拉算法
//    const std::pair<std::string, int>& lowestCostNode = findLowestCostNode(costs);
    std::pair<std::string, int> lowestCostNode = findLowestCostNode(costs, <#initializer#>);

    while (lowestCostNode != std::pair<std::string, int>()) {
        std::pair<std::string, int> cost = *costs.find(lowestCostNode.first);
        std::__umap_hashtable<std::string, int> neighbors = graph[lowestCostNode.first];
        for (const auto& item : neighbors) {
            std::pair<std::string, int> newCost(cost.first, cost.second + item.second);
            if (costs[item.first] > newCost.second) {
                costs[item.first] = newCost.second;
                parent[item.first] = std::to_string(lowestCostNode.second);
            }
        }
        processed.push_back(lowestCostNode);
//        const std::pair<std::string, int>& node = findLowestCostNode(costs);
        std::pair<std::string, int> node = findLowestCostNode(costs, <#initializer#>);
    }
}

static std::pair<std::string, int>
findLowestCostNode(std::__umap_hashtable<std::string, int>& cost) {
//     注意这下面这句代码的node是一个迭代器, 不是具体的结点！！！！卧槽！ TUT
//    auto node = cost.cbegin();
// TODO 注意: 这里使用 auto 会致使下面的 for循环中的 node = item; 出错！！！！
//  具体原因我也不知道。换成 *cost.begin()也是不行的！！！！
//  所以还是乖乖地不使用 auto 关键字吧！！！！！
//    auto node = *cost.cbegin();
    std::pair<std::string, int> node = *cost.cbegin();
//    auto lowest = cost.cbegin()->second;
//    int lowest = node.second;
    for (const auto& item : cost) {
        if (item.second < node.second) {
//            lowest = item.second;
            node = item;
        }
    }
    return node;
}
